package com.LeeCode;
/**
 * 爬楼梯
 * **/
public class Code070 {
    public static void main(String[] args) {
        int n = 45;
        System.out.println(new Code070().climbStairs1(n));


    }
    public int[] nums = new int[46];
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        }

        if(nums[n] == 0){
            nums[n] = climbStairs(n - 1) + climbStairs(n - 2);
        }
        return nums[n];
    }

    // 公式推导，不需要额外的空间存储中间结果
    public int climbStairs1(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

}
